//
// Created by Administrator on 2021/5/14.
//
#include <string>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    vector<int> number{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    vector<string> rome{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public:
    string intToRoman(int num) {
        string ans;
        transfer(ans, num, 0);
        return ans;
    }

    bool transfer(string &ans, int n, int index) {
        if (n == 0) return true;
        for (int i = index; i < rome.size(); ++i) {
            if (n >= number[i]) {
                ans += rome[i];
                if (transfer(ans, n - number[i], index)) return true;
            }
        }
        return false;
    }
};


class Solution2 { // 题解
    vector<int> number{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    vector<string> rome{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public:
    string intToRoman(int num) {
        string roman;
        for (int i = 0; i < number.size(); ++i) {
            while (num >= number[i]) {
                num -= number[i];
                roman += rome[i];
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};


class Solution3 { // 题解 硬编码
    const string thousands[4] = {"", "M", "MM", "MMM"};
    const string hundreds[10] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    const string tens[10] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    const string ones[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
public:
    string intToRoman(int num) {
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};


int main() {
    Solution3 sol;
    cout << sol.intToRoman(3) << endl;
    cout << sol.intToRoman(4) << endl;
    cout << sol.intToRoman(9) << endl;
    cout << sol.intToRoman(58) << endl;
    cout << sol.intToRoman(1994) << endl;
    return 0;
}